package tmp;

/*************************************************************************
 * Compilation: javac Diff Execution: java Diff filename1 filename2
 * Dependencies: In.java
 * 
 * Reads in two files and compute their diff. A bare bones version.
 * 
 * % java Diff input1.txt input2.txt
 * 
 * 
 * Limitations ----------- - Could hash the lines to avoid potentially more
 * expensive string comparisons.
 * 
 *************************************************************************/

public class Diff {

	public static void main(String[] args) {

		// read in lines of each file
		In in0 = new In("c:\\netmhc.html");
		In in1 = new In("c:\\netmhc1.html");
		String[] x = in0.readAll().split("\\n");
		String[] y = in1.readAll().split("\\n");

		// number of lines of each file
		int M = x.length;
		int N = y.length;

		// opt[i][j] = length of LCS of x[i..M] and y[j..N]
		int[][] opt = new int[M + 1][N + 1];

		// compute length of LCS and all subproblems via dynamic programming
		for (int i = M - 1; i >= 0; i--) {
			for (int j = N - 1; j >= 0; j--) {
				if (x[i].equals(y[j]))
					opt[i][j] = opt[i + 1][j + 1] + 1;
				else
					opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);
			}
		}

		// recover LCS itself and print out non-matching lines to standard
		// output
		int i = 0, j = 0;
		while (i < M && j < N) {
			if (x[i].equals(y[j])) {
				i++;
				j++;
			} else if (opt[i + 1][j] >= opt[i][j + 1])
				System.out.print("< " + x[i++]);
			else
				System.out.print("> " + y[j++]);
		}

		// dump out one remainder of one string if the other is exhausted
		
		while (i < M || j < N) {
			if (i == M)
				System.out.print("> " + y[j++]);
			else if (j == N)
				System.out.print("< " + x[i++]);
		}
		
	}

}
